package atop;

import java.util.Random;

/**
 * @创建人 MBY381
 * @创建时间 2022/4/15 11:14
 * @描述 暂无
 */
public class 快排寻找第k大的数 {
    static Random random = new Random();

    public static void main(String[] args) {
        int[] nums1 = new int[]{0xE3, 381, 8, 6, 4, 7, 9, 3, 5, 2, 1, 782, 696, 259, 0x15};
        System.out.println("正确答案：    [1, 2, 3, 4, 5, 6, 7, 8, 9, 21, 227, 259, 381, 696, 782]");
        int k=findKthLargest(nums1,3);

        System.out.println(k);
    }
    public static int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }

    public static int quickSelect(int[] nums, int left, int right, int indexKth) {
        int partition = getRandomPartition(nums, left, right);
        if (partition == indexKth) {
            return nums[partition];
        } else {
            return partition < indexKth ? quickSelect(nums, partition + 1, right, indexKth) : quickSelect(nums, left, partition - 1, indexKth);
        }
    }

    public static int getRandomPartition(int[] nums, int left, int right) {
        int index = random.nextInt(right - left + 1) + left;
        swap(nums, index, right);
        return sort(nums, left, right);
    }

    public static int sort(int[] nums, int left, int right) {
        int x = nums[right], index = left - 1;
        for (int j = left; j < right; ++j) {
            if (nums[j] <= x) {
                swap(nums, ++index, j);
            }
        }
        swap(nums, index + 1, right);
        return index + 1;
    }

    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}
